package com.sxkiler.demo.easy;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.*;
import com.sxkiler.demo.model.*;

/**
add-binary=二进制求和
<p>给你两个二进制字符串，返回它们的和（用二进制表示）。</p>

<p>输入为 <strong>非空 </strong>字符串且只包含数字&nbsp;<code>1</code>&nbsp;和&nbsp;<code>0</code>。</p>

<p>&nbsp;</p>

<p><strong>示例&nbsp;1:</strong></p>

<pre><strong>输入:</strong> a = "11", b = "1"
<strong>输出:</strong> "100"</pre>

<p><strong>示例&nbsp;2:</strong></p>

<pre><strong>输入:</strong> a = "1010", b = "1011"
<strong>输出:</strong> "10101"</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul>
	<li>每个字符串仅由字符 <code>'0'</code> 或 <code>'1'</code> 组成。</li>
	<li><code>1 &lt;= a.length, b.length &lt;= 10^4</code></li>
	<li>字符串如果不是 <code>"0"</code> ，就都不含前导零。</li>
</ul>

 */

/**
 如果 aa 的位数是 nn，bb 的位数为 mm，这个算法的渐进时间复杂度为 O(n + m)O(n+m)。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：

 如果字符串超过 3333 位，不能转化为 Integer
 如果字符串超过 6565 位，不能转化为 Long
 如果字符串超过 500000001500000001 位，不能转化为 BigInteger
 因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。

 我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

 具体的，我们可以取 n = max{ |a|, |b| }，循环 n 次，从最低位开始遍历。我们使用一个变量 carry 表示上一个位置的进位，初始值为 0。
 尾数为 (a(i) + b(i))mod2
 进位为 (a(i+1) + b(i+1) + carry) / 2
 */
public class addBinary {
    

    class Solution {
        public String addBinary(String a,String b) {
            StringBuffer ans = new StringBuffer();

            int n = Math.max(a.length(), b.length()), carry = 0;
            int len_a = a.length();
            int len_b = b.length();
            for (int i = 1; i <= n; ++i) {
                carry += i <= len_a ? (a.charAt(len_a - i) - '0') : 0;
                carry += i <= len_b ? (b.charAt(len_b - i) - '0') : 0;
                //尾值
                ans.append((char) (carry % 2 + '0'));
                //进位
                carry /= 2;
            }

            if (carry > 0) {
                ans.append('1');
            }
            ans.reverse();
            return ans.toString();
        }
    }

    @Test
    public void test(){
        Solution solution = new Solution();
        /**
        "11"
"1"
        */
        //int [] num1 = new int[]{1,3};
        //int [] num2 = new int[]{2};
        Assertions.assertEquals(solution.addBinary("11","1"),"100");
    }
}

